Moore's Voting Algorithm

Background Majority element: An element is the majority element if it occurs more than ⌊n/2⌋ times

Moore’s Voting Algorithm is a popular algorithm used to find the majority element in a sequence or array — that is, an element that appears more than n/2 times, where n is the total number of elements.

Key Idea:

The algorithm works in two passes and uses constant space (O(1)).

Steps:

1. Candidate Selection (First Pass):

   • Initialize a candidate element and a counter.

   • Traverse the array:

     • If the counter is 0, choose the current element as the candidate.

     • If the current element is the candidate, increment the counter.

     • Else, decrement the counter.

2. Verification (Second Pass):

   • After the first pass, you get a potential candidate.

   • In the second pass, count its actual occurrences to verify whether it appears more than n/2 times.

Example:

For the array [2, 2, 1, 1, 2, 2, 2]:

• Candidate after first pass: 2

• Second pass count: 5 (out of 7), which is > 7/2 ⇒ 2 is the majority element.

Time & Space Complexity:

• Time: O(n)

• Space: O(1)

Moore's Voting Algorithm is especially useful when working with large data sets or when memory efficiency is critical.

Single Pass Moore's Algorithm

The classic Moore’s Voting Algorithm is often described as two-pass (candidate selection + verification). However, if you're guaranteed that a majority element exists (i.e., it occurs more than ⌊n/2⌋ times), you can find it in just one pass, without needing to verify it afterward.